// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-20 20:56
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DateTrain;

import org.junit.jupiter.api.Test;

import java.util.*;

public class NetworkBecomesIdle {
    /**
     * 网络空闲时间
     * N定义的节点数量，M: 因为构建的图是有向图，所以边的数量是节点的两倍
     * INF: 定义的数量级别是1_000_000_000
     * dist:节点距离信息
     */
    static int N = 100010, M = N * 2, INF = 0x3f3f3f3f;
    static int[] he = new int[N], e = new int[M], ne = new int[M];
    static int[] dist = new int[N];
    /**
     * --------idx用于记录边的数量--------
     */
    int idx;

    /**
     * --------链式前向星--------
     */
    void add(int a, int b) {
        /*----当前边的指向节点----*/
        e[idx] = b;
        /*----和当前起点相同边的边索引信息（index of the e[]）----*/
        ne[idx] = he[a];
        /*----head[] 当前边的索引信息，可以看出a固定的，边和边之间不会相混----*/
        he[a] = idx++;
    }

    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Arrays.fill(he, -1);
        Arrays.fill(dist, INF);
        int n = patience.length;
        for (int[] e : edges) {
            /*-----链式前向星数据初始化-----*/
            /*-----因为是无向图，所以需要在两个节点都添加边的关系-----*/
            add(e[0], e[1]);
            add(e[1], e[0]);
        }
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(0);
        /*-----0代表了主服务器，0到主服务器的距离为0，其他服务器的记录显示是无穷，说明还没有被赋值-----*/
        dist[0] = 0;
        while (!d.isEmpty()) {
            int t = d.pollFirst();
            /*
                i：当前节点
                int[] ne: 和当前节点联通的所有节点的索引都存在里面
                int[] e: 节点信息
             */
            /*-----一次循环可以访问和当前节点联通的所有节点-----*/
            for (int i = he[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] != INF) {
                    /*-----当前节点已经有距离信息，则不需要赋值，当前路径已经不是最短路径，两点之间直线最短-----*/
                    continue;
                }
                /*-----图中每一条边的路径长度都是一，dist表示的是当前服务器j到主服务器的距离-----*/
                dist[j] = dist[t] + 1;
                /*-----因为所有整个图是联通图，所以可以遍历完所有节点-----*/
                d.addLast(j);
            }
        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
            int di = dist[i] * 2, t = patience[i];
            int cur = di <= t ? di : (di - 1) / t * t + di;
            if (cur > ans) {
                ans = cur;
            }
        }
        return ans + 1;
    }


    class Solution {
        /**
         * --------容易理解的解法--------
         * 1 邻接链表使用HashMap构建
         * 2 BFS遍历可以访问图中到开始节点的最远路径信息，即访问到当前节点，如果当前节点信息仍然是初始化状态，说明当前路径是最短路径
         * 3 BFS遍历需要使用辅助栈，类似于树的层序遍历
         * 4 题解中使用int[] 数组实现对距离的初始化，通过BFS获取所有节点到根节点信息
         */
        public int networkBecomesIdle(int[][] edges, int[] patience) {
            /*-----节点数量-----*/
            int n = patience.length;
            /*-----hash结构创建临接链表-----*/
            Map<Integer, List<Integer>> graph = new HashMap<>();
            /*-----邻接表初始化-----*/
            for (int[] edge : edges) {
                List<Integer> l1 = graph.getOrDefault(edge[0], new ArrayList<>()),
                        l2 = graph.getOrDefault(edge[1], new ArrayList<>());
                l1.add(edge[1]);
                l2.add(edge[0]);
                graph.put(edge[0], l1);
                graph.put(edge[1], l2);
            }
            /*-----节点距离信息-----*/
            int[] distance = new int[n];
            distance[0] = -1;
            /*-----BFS遍历使用辅助栈-----*/
            Deque<int[]> deque = new ArrayDeque<>();
            /*-----初始状态是主服务器到主服务器-----*/
            deque.addLast(new int[]{0, 0});
            while (!deque.isEmpty()) {
                int[] cur = deque.pollFirst();
                /*-----BFS遍历，从邻接链表中获取直接相邻节点并且距离+1-----*/
                for (int other : graph.get(cur[0])) {
                    /*
                        distance数组长度就是节点数量大小，distance数组中初始化中除了主服务器距离为-1其他为0，所以通过邻接表可以
                        获取和当前节点联通的所有节点的信息，如果当前节点的信息还没有初始化就说明当前节点路径是最短的，否则路径不是最短的
                     */
                    if (distance[other] == 0) {
                        distance[other] = cur[1] + 1;
                        deque.addLast(new int[]{other, cur[1] + 1});
                    }
                }
            }
            int ans = 0;
            for (int i = 1; i < n; i++) {
                /*-----遍历所有节点到主服务器的距离信息，返回用时最久的信息作为返回值-----*/
                int d = distance[i] * 2, p = patience[i];
                ans = Math.max(ans, (d - 1) / p * p + d);
            }
            return ans + 1;
        }
    }


    @Test
    public void shout() {
//        int[][] edges = {{0, 1}, {1, 2}};
//        int[] patient = {0, 2, 1};
        int[][] edges = {{0, 1}, {0, 2}, {1, 2}};
        int[] patient = {0, 10, 10};
        System.out.println(networkBecomesIdle(edges, patient));
    }

}



